package recursivecode.trymodel.rangemodel;

/**
 * 功能描述:纸牌游戏: A B 两人,在牌堆中,A先抽取,B后抽取, 直到牌堆中无牌,各自手中的 牌总数 和 谁最大,谁获胜
 * 2024/07/16
 *
 * @author ZhangYi
 */
public class CardGame {
	public static void main(String[] args) {
		int[] arr = {1, 100, 4, 7};
		System.out.println(getMaxCards(arr));
		System.out.println(getMaxCardsFromCache(arr));
	}

	/**
	 * 从缓存中获取max卡
	 *
	 * @param arr arr
	 * @return int
	 * @author ZhangYi
	 */
	private static int getMaxCardsFromCache(int[] arr) {
		if (arr == null || arr.length == 0) {
			return 0;
		}
		int N = arr.length;
		int[][] firstCache = new int[N][N];
		// 由于缓存是二维数组,所以需要初始化 , int 默认为0; 所以不需要额外的初始化的流程
		int[][] secondCache = new int[N][N];

		for (int i = 0; i < N; i++) {
			firstCache[i][i] = arr[i];
		}

		// 控制每一列的索引下标
		for (int columnIndex = 1; columnIndex < N; columnIndex++) {
			int L = 0;
			int R = columnIndex;
			while (L < N && R < N) {
				firstCache[L][R] = Math.max(arr[L] + secondCache[L + 1][R], arr[R] + secondCache[L][R - 1]);
				secondCache[L][R] = Math.min(firstCache[L + 1][R], firstCache[L][R - 1]);
				L++;
				R++;
			}
		}
		return Math.max(firstCache[0][N - 1], secondCache[0][N - 1]);
	}


	/**
	 * 获取max卡
	 *
	 * @param arr arr
	 * @return int
	 * @author ZhangYi
	 */
	private static int getMaxCards(int[] arr) {
		if (arr == null || arr.length == 0) {
			return 0;
		}
		return Math.max(firstHand(arr, 0, arr.length - 1), secondHand(arr, 0, arr.length - 1));
	}

	/**
	 * 第一手: A 先抽取
	 *
	 * @param arr arr
	 * @param L   l
	 * @param R   右
	 * @return int
	 * @author ZhangYi
	 */
	private static int firstHand(int[] arr, int L, int R) {
		if (L == R) {
			return arr[L];
		}
		return Math.max(arr[L] + secondHand(arr, L + 1, R), arr[R] + secondHand(arr, L, R - 1));
	}

	/**
	 * 第二手 A 后抽取
	 *
	 * @param arr arr
	 * @param L   左
	 * @param R   右
	 * @return int
	 * @author ZhangYi
	 */
	private static int secondHand(int[] arr, int L, int R) {
		if (L == R) {
			return 0;
		}
		return Math.min(firstHand(arr, L + 1, R), firstHand(arr, L, R - 1));
	}


}
